package nan.priorityQueue;

public class Heap {
    //向下调整是创建堆的一个核心操作
    //前提条件：要求当前被调整节点的左右子树已经是堆了
    private void shiftDown(int[] arr,int size,int index){//index是起始位置,size
        //表示当前数组的有效元素大小
        int parent=index;//当前父节点的下标
        int child=parent*2+1;//当前出发节点的左子树的下标
        while(child<size){//当前节点的左子树存在
            //需要找到左右子树中较大的那个
            if(child+1<size && arr[child+1]>arr[child]){//如果右子树存在
                // 并且右子树的值大于左子树
                child=child+1;//让child指向左右子树较大的元素，即右子树。
                // 如果左子树大，child不变还是指向左子树
            }
            //拿父节点和刚才找到的较大的节点的值再做比较,看是否符合大堆的要求
            if(arr[parent]<arr[child]){
                //不满足大堆的要求就交换这两个元素，只是在数组中把这两个元素的位置交换了
                int tmp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=tmp;
            }else{
                break;//调整完毕，已经把父元素放在合适的位置了
            }
            //更新parent和child的位置以备下次调整
            parent=child;
            child=2*parent+1;
        }
    }

    //向上调整
    public void shiftUp(int[] arr,int size,int index){
        int child =index;
        int parent=(child-1)/2;
        while(child>0){
            if(arr[parent]<arr[child]){
                int tmp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=tmp;
            }else{
                break;
            }
            child=parent;
            parent=(child-1)/2;
        }

    }

    //建堆操作时间复杂度O(N)
    public void createHeap(int[] array){
        //基于向下调整的建堆
        //从后往前遍历数组，针对每个下标都去进行向下调整即可
        //从叶子节点往下进行查找是不合适的，从第一个非叶子节点开始进行向下调整，就可以
        // 通过最后一个节点找到父节点即可
        for(int i=(array.length-1-1)/2;i>=0;i--){
            shiftDown(array,array.length,i);
        }
    }

    //往堆中插入元素
    private int[] arr=new int[100];//表示当前存储堆的数组
    private int size=0;
    //{1,0,0,0,0,0,0,0,0,},size是一个索引
    public void offer(int val){
        if(size>= arr.length){//插入失败，已经满了
            return;
        }
        arr[size]=val;//把这个元素尾插到数组末尾
        size++;
        //把最后这个元素进行向上调整
        shiftUp(arr,size,size-1);
    }
    //使用向上调整建堆
    public void createHeap2(int[] arr){
        //循环遍历数组，把元素通过offer方法插入即可
        for(int x:arr){
            offer(x);
        }
    }

    //删除操作(一定是删除堆顶元素)
    public Integer poll(){
        if(size==0){
            return null;
        }
        int result=arr[0];//0号元素是要被删除的那个元素
        //交换0号元素和size-1号元素
        int tmp=arr[0];
        arr[0]=arr[size-1];
        arr[size-1]=tmp;
        //size--,把最后这个元素删除掉
        size--;
        //从0号元素开始进行向下调整
        shiftDown(arr,size,0);
        return result;
    }
}
